package com.yulan.Stack;

import org.junit.Test;

import java.util.Stack;

/**
 * 739. 每日温度
 *  使用一个单调栈，当栈顶元素比当前遍历的元素大时，直接入栈，否则，就将栈中所有小于该元素的元素弹出，并且计算对应的结果
 */
public class LeetCode_739 {
    public int[] dailyTemperatures(int[] T) {
        Stack<Integer> stack = new Stack<>();
        int n = T.length;
        stack.push(-1);
        int[] res = new int[n];
        for(int i = 0 ;i<T.length;i++){
            while(stack.peek()!=-1 && T[i] > T[stack.peek()]){
                int cur = stack.pop();
                res[cur] = i - cur;
            }
            /**
             * 如果遇不到比它大的元素，先将其下标压入栈，直到遇到比栈顶元素大的那个数字出现再计算结果
             */
            stack.push(i);
        }
        return res;
    }
    @Test
    public void test(){
        int[] arr = {73, 74, 75, 71, 69, 72, 76, 73};
        for(int i:dailyTemperatures(arr))
            System.out.print(i+" ");
    }

}
